The present invention relates to interleavers as employed, for example, in the field of information and encoding technology for scrambling information.
In the field of conventional technology, interleavers are employed, e.g., in data communication. There, binary digits are often transferred in the form of transmit symbols, which are then, in transmission e.g. via a mobile radio channel, interfered with. As in most cases several successive symbols are affected by an interference, which is customarily referred to as burst errors, scrambling techniques are employed. This means that individual digits in an original information word are scrambled such that same are no longer successive in the transmission. This results in the fact that, in the occurrence of burst errors and subsequent descrambling, the burst errors will be ripped apart and thus distributed across the information word. These technologies may also be used in the storage of data, such as with audio CDs, for example. Ideally, the burst errors occurring are ripped apart, thus leading to individual errors that are correctable. For the scrambling and/or descrambling, so-called interleavers are used.
In telecommunications, error-correcting codes are used for the protection from transmission errors. Here, convolution encoders, block encoders, etc. may be employed, for example. There, turbo codes are one of the highest-performance code classes, and their capability of correcting transmission errors outperforms that of convolution codes by far, cf. Claude Berrou, Alain Glavieux, and Punya Thitimajshima: “Near Shannon-Limit Error-Correcting Coding and Decoding: Turbo Codes”, Intern. Conf. on Communication, pages 1064-1070, 1993.
Turbo-code interleavers are an integral component of turbo encoders as well as of the associated turbo decoders. FIG. 11 illustrates a schematic block diagram of such a turbo encoder 1100. The turbo encoder 1100 comprises a 1st component encoder 1105, a turbo code interleaver 1110, a 2nd component encoder 1115 and a puncturer 1120. An information word, i.e. a vector consisting of information bits that may for example be specified by an index range from 0 to Infoword_Len−1, Infoword_Len corresponding to the word length, is encoded by feeding a 1st copy directly to the puncturer 1120, a 2nd copy of the vector to the 1st component encoder 1105 and a 3rd copy to the turbo-code interleaver 1110. The turbo-code interleaver 1110 permutes the bits of this sector, i.e. it resorts these bits or digits, changes their order and forwards the thus permuted vector of the same length of Infoword_Len to the 2nd component encoder 1115.
Both component encoders 1105 and 1115 are generally the same and represent a recursive convolution encoder providing at least one parity bit, or several, as the case may be, at its output or outputs per input bit. In FIG. 11, two parity bits each for the two component encoders 1105 and 1115 are shown.
FIG. 12 shows an example of a component encoder, which may be realized in the form of a convolution encoder, for example. FIG. 12 shows an example of a recursive convolution encoder having 2 parity bits per input bit and a memory length of 3. FIG. 12 shows 3 flip-flops 1200, 1205 and 1210, which are linked to one another via summation members and coupling branches. The example represented in FIG. 12 shows that, for one input bit present at the input 1215, 2 parity bits each are output at the outputs 1220 and 1225. Furthermore, the 3 flip-flops 1200, 1205 and 1210 correspond to 3 one-bit memories realizing the memory length 3. Each of the 3 flip-flops 1200, 1205 and 1210 stores one bit, i.e. binary “0” of “1”, for one unit of time and outputs same at the respective output. At the beginning of the next unit of time, the bit present at the input of a flip-flop is stored and then output. Therefore, the arrangement in FIG. 12 may also be considered a conventional shift register. The plus symbols mark the summation members, i.e. those nodes at which binary additions are performed, the binary addition corresponding to the binary EXOR operation. In the lower part of FIG. 12, a feedback branch 1230 is to be seen, by means of which the content of the shift register is fed back to its input 1215. Therefore, FIG. 12 shows an example of a convolution encoder that may be employed as a component encoder in the representation of FIG. 11.
According to the example of FIG. 11, the parity bits of the component encoders 1105 and 1115, the systematic bits, which correspond to the information bits, are provided to a puncturer 1120. From FIG. 11, it can be seen that the puncturer 1120 comprises 5 inputs and only one output. In the puncturer 1120, a parallel-serial conversion of the 5 inputs to the one output takes place, wherein, however, bits present at the inputs may also simply discarded and not forwarded to the output. This may be controlled via a puncture pattern, for example, which determines which bits of the 5 inputs are to be forwarded to the output. The puncturer may, for example, forward to the output each systematic bit but only each 2nd bit of the 4 parity-bit inputs. As, for each information word to be transferred, a total of Infoword_Len bits are present at each of the 5 inputs, a maximum of 5×Infoword_Len bits may be output.
A suitable puncture pattern may serve to achieve an adjusted quantity of Codeword_Len bits being output by the puncturer so that the length of a code word output, which is comprised of the code bits, will be Codeword_Len. The ratio Infoword_Len/Codeword_Len is the code rate of the turbo code. For the above example, the code rate may be adjusted from ⅕ to 1 by the puncturer.
After transmission of the code bits, i.e. the code word, via a transmission channel, bits interfered with in the receiver, for example, which may be present there in the form of soft bits, are processed. In other words, binary digits may be represented at a higher resolution in the receiver, i.e. for a binary digit “0” or “1” transmitted, several binary digits may be used in a receiver. In this manner, reliability information of the individual binary digits may be taken into account in the decoding, for example. A turbo decoder now has the task of correcting transmission errors.
A turbo decoder adapted to the turbo encoder shown in FIG. 11 is shown in FIG. 13. The turbo decoder comprises a de-puncturer 1300, a 1st component decoder 1305, a 2nd component decoder 1310, a turbo-code interleaver 1315 and a turbo-code deinterleaver 1320. The structure of the turbo decoder shown in FIG. 13 already shows that the turbo-code interleaver 1315 and the turbo-code deinterleaver 1320 are of central importance.
A turbo decoder operates in an iterative manner, i.e., in contrast to Viterbi decoders for convolution codes, here, each component decoder is not used only once but once per iteration, wherein several iterations may be performed, the typical number of iterations ranging from 3 to 8. The de-puncturer 1300 determines the systematic bits as well as the parity bits of the 1st component and the 2nd component from the code bits received. The parity bits of the 1st component are fed to the 1st component decoder 1305 and the parity bits of the 2nd component are fed to the 2nd component decoder 1310. In each iteration, the 1st component decoder 1305 calculates, based on its inputs, i.e. based on the parity bits of the 1st component, on the systematic bits, as well as on the extrinsic information of the 2nd component, an output signal, which may be referred to as extrinsic information of the 1st component.
For each of the Infoword_Len systematic bits, there is also extrinsic information, i.e., this output of the 1st component decoder 1305 is a vector of pieces of Infoword_Len extrinsic information. Apart from that, the 1st component decoder 1305, via a 2nd output, provides a vector of Infoword_Len decoded, i.e. estimated, information bits. The two vectors of the systematic soft bits and the extrinsic information of the 1st component are permuted in the turbo-code interleaver 1315, i.e., each vector is scrambled individually and with the same permutation as in the turbo encoder, as is represented in FIG. 11, for example.
Similarly, the 2nd component decoder 1310 calculates as an output, based on its inputs, a vector of the length Infoword_Len of pieces of extrinsic information of the 2nd component. Same is fed back to the 1st component decoder 1305 via the turbo-code deinterleaver 1320 so that the former may begin the next iteration. During the iterations, the 1st and the 2nd component decoders 1305; 1310 exchange their respective extrinsic information via the turbo-code interleaver 1315 and the turbo-code deinterleaver 1320, respectively. Here, the turbo-code de-interleaver 1320 corresponds to the turbo-code interleaver 1315 such that a vector of the length Infoword_Len, once having been permuted by the turbo-code interleaver 1315 with the result thereof afterwards having been permuted by the turbo-code deinterleaver 1320, is again identical to the original vector.
Among other things, the turbo-code interleaver 1315 serves to ensure high distances between the permuted code words. In general, the Hamming distance between code words may be used as a measure, which corresponds to the number of bits in which 2 code words A and B differ from each other. If code word A is transferred, code word B will instead erroneously be selected by the receiver when these bits were corrupted by the channel. This is the case as soon as half of these bits are corrupted. Naturally, the probability of a wrong code word B being selected becomes smaller as the Hamming distance between A and B increases, cf., e.g., Todd K. Moon “Error Correction Coding”, Wiley, 2007, ISBN 978-0-471-64800-0.
Now, the turbo-code interleaver 1100 or 1315 is to see to it that the distances between each possible code word A and all other possible code words B are rendered large. Solving this task may be explained in a somewhat simplified manner as follows. The Hamming distance between 2 code words A and B may be calculated as the Hamming weight of vector A plus B, the weight meaning the number of ones of the vector. As mentioned above, the plus symbol here represents a binary addition, which corresponds to an XOR operation between one bit of A and B each, i.e. bit 0 of A is linked to bit 0 of B, Bit 1 of A is linked to bit 1 of B, bit 2 of A is linked to bit 2 of B, and so on.
Turbo codes are linear, i.e. they possess the property that A plus B is a valid code word when A and B are valid code words. Therefore, as the code word A, the zero vector may also be assumed a transferred code word. Then, the distances to all other code words B are simply the Hamming weights of these other code words. Due to the linearity property, the distance distribution, i.e. the histogram of the distances occurring to all possible code words B, is identical for each code word A and therefore also for the zero vector. If same is assumed the code word A, the distance distribution will be identical to the weight distribution of all possible code words.
According to the above explanations, a turbo encoder, such as represented in FIG. 11, outputs a zero vector at its output when its input is a zero vector. Based on the above considerations, the aim of the turbo-code interleaver 1110; 1315 therefore is seeing to it that a maximum weight is generated at the output when a vector other than the zero vector is present at the input.
The minimum weight dmin of all code words is of particular importance as, in a transmission of the zero word, corruption towards the minimum weight code words is most probable. Analogously, in transferring any code word A, what is most probable is a corruption towards a code word B, which has a minimum distance of dmin to code word A.
It is the minimum distance dmin which also largely determines the shape of the word error rate graph. In such word error rate graphs, the word error rates WER (i.e. the ratio of the incorrectly decoded code words to the total number of code words transferred) are plotted versus an increasing signal-to-noise ratio (SNR) for a static non-frequency-selective channel with additive white Gaussian noise (AWGN). In FIG. 10a, such a graph is represented by means of a dashed line. Observing this line, it can be seen that same comprises a portion between 1.2 and 1.6 dB, in which the WER graph drops more steeply, followed by a shallower graph portion, which is referred to as the so-called error floor. The position of the error floor is mainly caused by the code words having the minimum distance dmin from the code word transferred.
For commercial systems, it is therefore desired that such an error floor be naturally limited, as too high a WER renders the data transmission unreliable, i.e. causes signal failures, and as the WER may also not be substantially reduced within the error floor, even by increasing the SNR.
For this reason, a considerable amount of research work has been invested in the reduction of the error floor since the turbo codes emerged, cf., for example, Marco Breiling, “Analysis and Design of Turbo Code Interleavers”, Shaker Verlag, Aachen, 2002 ISBN 3-8322-0302-8, and S. Crozier and P. Guinand: “High-performance low memory interleaver banks for turbo-codes”, in Proc. of the 54th IEEE Veh. Tech. Conf (VTC'01), Atlantic City, pp. 2394-2398, October 2001.
For this purpose, manifold approaches for optimizing also turbo-code interleavers were made, as several proposals were made regarding the UMTS standardization (UMTS=Universal Mobile Telecommunications System), cf. Johan Hokfelt, Ove Edfors, and Torleiv Maseng: “Interleaver design for turbo codes based on the performance of iterative decoding”, Intern. Conf. on Communications, Communications Theory Mini Conference, pages 93-97, 1999.
The above considerations already show that the generation of weight in the turbo encoder should be taken into account so as to make the methodology behind the design of turbo-code interleavers comprehensible. A code word having the weight dmin will not come into existence unless the information word has a lower weight, as same itself contributes to the code word in the form of a systematic portion. When the information word is represented by a vector having one single one: 00 . . . 010 . . . 0, then what happens in the 1st component encoder 1105 is the following: before this one enters the component encoder 1105, the latter outputs only zeros at its outputs as the internal shift register of the component encoder 1105 contains zeros only, cf. FIG. 12.
After the one has reached the component encoder, the shift register will no longer contain only zeros, and, by means of the feedback branch 1230, the flip-flops 1200, 1205 and 1210 will no longer all at the same time be zero for the rest of this information word. This means that, as of the point in time at which a single one is input, this component encoder will provide many ones at its outputs 1220; 1225. Thus as a rule, the two streams of parity bits have a large weight, and code words generated by one single one correspondingly also have a large weight.
The picture is different when, at the input of a component encoder, there is present a vector with two ones having a certain distance to each other, wherein, here, distance is meant in the sense of a spacing of the two positions within the vector. The component encoder shown in FIG. 12 provides a small output weight for the following input vectors among others:    00 . . . 0100000010 . . . 0,    00 . . . 01000000000000010 . . . 0,    00 . . . 010000000000000000000010 . . . 0,i.e. each time the distance of the ones is a multiple of 7 positions. The portion of the vector between the beginning and the terminating one, including these ones, is in the following to be referred to as an error pattern. This term originates from the fact that these patterns are responsible for code words erroneously output by the decoder in a faulty transmission of the zero code word. Each first one results in the shift register no longer containing zeros only and therefore beginning to output bits unequal to zero, while the terminating one sees to it that the shift register will again contain zeros only, i.e. return to the so-called zero state, and that therefore only zeros will be output thereafter.
While 10000001 is an error pattern, 1000001, i.e. the distance between the ones is 6 positions only, and 100000001, i.e. the distance is 8 positions, and so on, are not an error pattern, i.e. here the shift register does not, with the 2nd one, return to the zero state and therefore will subsequently continue to output ones.
Therefore, for increasing dmin, a turbo-code interleaver should permute a maximum of error patterns at the input of the 1st component decoder 1305, the error patterns generating parity bits of a possibly only low weight, such that same are mapped to sequences at the input of the 2nd component decoder 1310, same being no error patterns and therefore having to generate a high parity weight.
As already explained above, the quality of the turbo-code interleaver directly affects the error floor of the word error rate graph. One further important issue is the implementability of the turbo-code interleaver. In principle, each turbo-code interleaver is implementable as an address table, i.e. for each input bit of the 1st and/or 2nd component, a table sequentially states the address this bit is to be read from and/or written to, for the respective other component encoder to be able to process same. The process of interleaving may be expressed as reordering information bits in memories: when, prior to interleaving, an information bit is to be found in address i of a first memory, then, after interleaving, it will be found in address Addr[i] of either also the first or a second memory. For 10,000 information bits, for example, this address table would comprise 10,000 entries, each having 14 bits, for the representation of addresses up to 10,000. These addresses may be stored in a separate ROM (ROM=read only memory) or RAM (RAM=random access memory), which involves substantial expenditure in the implementation. This problem is made even more critical when the turbo code is to support several word sizes, such as is frequently the case in modern communications systems, for example. In this case, a separate table would be necessitated for each word size, with the RAM and/or ROM demands summing up.
For this reason, ambitions directed at selecting an algorithmically representable turbo-code interleaver are starting to be made in the field of conventional technology also. Here, the permutation address for each information bit is calculated by means of a regulation that may be represented by few arithmetic operations as well as the use of few parameters. These parameters may assume different values for each word size and be stored in small RAM and/or ROM tables.
In the early phases of turbo codes, random permutations were frequently chosen as turbo-code interleavers, as is represented in FIG. 14, for example. FIG. 14 shows a random turbo-code interleaver based on an interleaver length of 1146 bits. The representation in FIG. 14 shows the bit position of the 1st component on the ordinate and the bit position of the 2nd component on the abscissa. The respective allocation is represented by a cross, wherein the distribution of the crosses indicates the random nature of the turbo-code interleaver. With respect to random interleavers it is shown that same, with almost 100% certainty, will permute error patterns at the input of the 1st component decoder to error patterns at the input of the 2nd component decoder, with the result of a code word having a low weight being generated, cf. Sergio Benedetto and Guido Montorsi: “Unveiling Turbo Codes: Some Results on Parallel Concatenated Coding Schemes”, IEEE Trans. on Inform. Theory, 42(2):409-428, 1996.
The WER of a random interleaver is shown next to other ones in FIG. 10a in the form of a dashed line and designated with “RAND ILV.” and. Here, the error floor is clearly recognizable. One further drawback in random interleavers is that they are not representable in an algorithmic manner, thus having to be stored in the form of a table.
In the context of conventional technology, linear congruent interleavers are further known. As opposed to random interleavers, these interleavers are strictly describable in mathematical terms. The address Addr[i] of an information bit i may be calculated according to the formulaAddr[i]=(C×i)mod K, wherein mod represents the modulo operation, K is the information word size and C is a constant that is relatively prime with respect to K and represents the increment between successive addresses. These interleavers have a high error floor, which is why they are only rarely employed in practice.
In the early phases of the turbo codes, rectangular interleavers were also used in research instead of the random interleavers. One example of a rectangular interleaver is represented in FIG. 15. FIG. 15 shows a rectangular representation with 3 rows and 4 columns with the respective read and/or write indices entered in the respective elements. As FIG. 15 shows, the information word size is equal to the product of row and column numbers. The bits to be permuted are written to same in a row-by-row and read from same in a column-by-column manner. The performance of these interleavers is also insufficient.
The extreme examples of the random interleaver on the one hand and the rectangular interleaver or linear congruent interleaver on the other hand show that both too random and too structured a setup of a turbo-code interleaver will result in poor efficiency of the code.
From the literature, s-random interleavers are further known, cf. S. Dolinar and D. Divsalar: “Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations”, Jet Propulsion Lab, TDA Prog. Rep., 42-122: 56-65, 1995, wherein the permutation is pseudo-random to a certain degree, with, however, randomness being subjected to some limitations with regard to the distances the positions of 2 arbitrary bits in the 1st and 2nd components are allowed to have. These s-random interleavers serve to achieve a relatively good performance of the turbo code. The drawback here is that, similar to the random interleavers, no algorithmic calculation formula of the interleaver may be given.
An interleaving possessing many properties of the s-random interleaver, while still be algorithmically describable, is the dithered relatively prime interleaver, cf. S. Crozier and P. Guinand: “High-performance low-memory interleaver banks for turbo-codes”, in Proc. of the 54th IEEE Veh. Tech. Conf (VTC'01), Atlantic City, pp. 2394-2398, October 2001. This interleaver is a mixture of pseudo-randomness and structure and has prescribed distances of the bit positions. It is based on the linear congruent interleaver with an additionally superimposed local permutation so as to break up the rigid structure of the linear congruent interleaver.
A further known interleaver is the UMTS or 3GPP interleaver (3GPP=Third Generation Partnership Project), see W-CDMA 3GPP TS 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing and channel coding (FDD), as well as Hirohito Suda and Akira Shibutani: “Interleaving method, interleaving apparatus, turbo encoding method, and turbo encoder”, European Patent 1 030 455 B1, 1999. The basic principle behind the turbo-code interleaver used in the 3GPP standard is a rectangular interleaver, in the following referred to as a frame interleaver, in which, in addition, intra- and inter-row interleaving is performed. This means that first, in a 1st step, the information bits are written to a rectangular interleaver in a row-wise manner. Subsequently, additional permutations are performed within each row, which is the so-called intra-row interleaving, the permutation in each row being different. In the 3GPP interleaver, this permutation is performed based on cycles generated in a Galois field by means of raising a primitive element to a higher power. The intra-row interleaving thus being generated is roughly equivalent to pseudo-random permutation.
Subsequently, in a 3GPP interleaver, complete rows are interchanged, which is the so-called inter-row interleaving. Intra- and inter-row interleaving having been effected, the rectangular frame interleaver permuted such is read column by column.
In the case of the 3GPP interleaver, additional expenditure is necessitated for adapting the interleaver to the word size. For this purpose, dummy bits are appended to the information word prior to permutation so that the word supplemented such completely fills a rectangular interleaver, wherein the length of the filled-up input word will then result from the product of row and column numbers. After the permutation, these dummy bits are removed, i.e. a so-called pruning is performed. The permutation in the 3GPP interleaver is therefore comprised of a series of individual operations.
The drawback caused by the treating of dummy bits, i.e. the insertion, the part in the permutations performed and the removal thereof, is that additional processing time, consumption of resources, such as additional storage requirements, and additional implementation expenditure, i.e. complexity, will be necessitated.
For doing without the actual adding and subsequent removing of the dummy bits to or from the “true” information bits, what would be useful is calculating the index of an interleaved information bit directly, i.e. after the complete interleave process and the reading from the interleaver memory. What would also be desired is a calculation regulation capable of directly indicating the index of an information bit in the interleaved information word, as it would result from the above-mentioned process of dummy-bit addition, interleaving and dummy-bit removal, without, however, this adding and removing of dummy bits having to actually be effected.
There is, however, no way of giving a simple calculation regulation as the 3GPP interleaver has the following drawback: the frame interleaver of this standard is a rectangular interleaver, the number of elements of which is the product of the row and column numbers. As the block size may be arbitrarily chosen, inevitably—as described above—additional dummy bits are inserted and removed after the interleaving. After the insertion of the dummy bits, all rows of the frame interleaver have the same length, which is why all intra-row interleavers will operate with the same row length. Therefore, the dummy bits are generally scattered across the entire frame interleaver by means of the intra- and inter-row permutations. In addition, the number of dummy bits may differ in the individual rows. The irregular distribution of the dummy bits across the entire frame interleaver does not allow any simple direct calculation for the index of the interleaved information bit (after intra- and inter-row permutation and reading-out) as these irregularities need to be accounted for in the formula.
In the cdma2000 or 3GPP interleaver (see CDMA-2000 3GPP2 C.S0002-C Version 2.0 Physical Layer Standard for cdma2000 Spread Spectrum Systems Revision C, and Douglas N. Rowitch and Fuyun Ling: “Turbo Code Interleaver using Linear Congruential Sequence”, U.S. Pat. No. 6,304,991 B1, 1998, and Steven J. Halter: “Random-Access Multi-Directional CDMA2000 Turbo Code Interleaver”, U.S. Pat. No. 6,871,303 B2, 2001) too, basically, a frame interleaver in the form of a rectangular interleaver is used, in which intra- and inter-row interleaving is performed. Here, the intra-row interleaving is based on linear congruent interleaving, which is also to effect a quasi-random permutation, while the inter-row interleaving is achieved by means of a digit-wise reversal of the bit representation of the respective row index (bit reversal).
The 3GPP2 interleaver also necessitates additional effort for adapting the interleaver to the word size chosen, as the product of row and column numbers is normally unequal to the information word size. Therefore, 2 candidate addresses are generated for one information bit, the addresses positioned between zero and the product of the row and column numbers. In case the first candidate address is valid, i.e. lies between zero and the information word size, it is used, otherwise it is discarded and the second candidate address is used, which in this case is valid in each case (this may be proven for the algorithm used).
While the frame interleaver of the 3GPP2 standard is a rectangular interleaver, the information word size may here be selected at certain levels, and each information word size has its own parameter sets for the interleaver. As a rule, the information word sizes are unequal to the number of elements of the rectangular frame interleaver (product of row and column numbers). Although, with this interleaver design, no filling up of the frame interleaver with dummy bits is necessitated, here, too, simple direct calculation of the address of an information bit is not possible.
For it is a characteristic feature of the 3GPP2 interleaver that the address calculation regulation contains a counter-value unequal to the index of the bit to be permuted. For example, if a block size of 378 bits is chosen, then the bit index will range from 0-377, while the counter-value transitions through all values from 0 to 511. For calculating the address of the bit having the index zero, the counter-value of zero is used, but as early as for the bit having the index 3, it is not the counter-value 3, which is discarded, but 4 that is used. This is due to the algorithm from the 3GPP2 standard, which generates candidate addresses that for some indices are invalid. This is caused by the fact that the inter- and intra-row interleaving will assume that each row or column is complete and of the same length.
Without the above-mentioned counter and the generation of possibly invalid candidate addresses, the calculation thereof is not feasible. This method is disadvantageous exactly in the generation of invalid addresses, which need to be discarded, which in turn results in more processing time and/or higher implementation expenditure for the parallel generation of two addresses.